/**
 * //Given an array of integers temperatures represents the daily temperatures,
 * //return an array answer such that answer[i] is the number of days you have to wait
 * //after the iᵗʰ day to get a warmer temperature. If there is no future day for
 * //which this is possible, keep answer[i] == 0 instead.
 * //
 * //
 * // Example 1:
 * // Input: temperatures = [73,74,75,71,69,72,76,73]
 * //Output: [1,1,4,2,1,1,0,0]
 * //
 * // Example 2:
 * // Input: temperatures = [30,40,50,60]
 * //Output: [1,1,1,0]
 * //
 * // Example 3:
 * // Input: temperatures = [30,60,90]
 * //Output: [1,1,0]
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= temperatures.length <= 10⁵
 * // 30 <= temperatures[i] <= 100
 * //
 * //
 * // Related Topics 栈 数组 单调栈 👍 1332 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID00739DailyTemperatures {
    public static void main(String[] args) {
        Solution solution = new ID00739DailyTemperatures().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {

            int n = temperatures.length;
            if (n == 1) return new int[]{0};
            int[] answer = new int[n];
            Stack<Integer> indexStack = new Stack<>();

//        for(int i = 0; i < n; i++){ //暴力O（n²） 超时
//            int tmp = 1;
//            int lowTemp = temperatures[i];
//            while(i+tmp < n && lowTemp >= temperatures[i+tmp]){
//                tmp++;
//            }
//            if(n == i+tmp){
//                answer[i] = 0;
//            }else{
//                answer[i] = tmp;
//            }
//        }

            indexStack.push(0);
            for (int i = 1; i < n; i++) {
                int top = indexStack.peek(); //topValue
                while (!indexStack.isEmpty() && temperatures[i] > temperatures[top]) {//when meet temperature greater than top value. found previous larger value;
                    answer[top] = i - top;
                    indexStack.pop();
                    if (indexStack.isEmpty()) break;
                    top = indexStack.peek();

                }
                indexStack.push(i);

            }


            return answer;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}